package j2024.j202412;

public class j1229 {
    /**
     * 105. 从前序与中序遍历序列构造二叉树
     * 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历，
     * inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
     */
    int preIndex = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeNode(preorder,inorder,0,preorder.length-1);
    }
    private TreeNode buildTreeNode(int[] preorder, int[] inorder, int begin, int end) {
        if (begin > end) return null;
        TreeNode root = new TreeNode(preorder[preIndex]);
        int rootVal = findRootVal(inorder,begin,end,preorder[preIndex]);
        preIndex++;
        root.left = buildTreeNode(preorder,inorder,begin,rootVal-1);
        root.right = buildTreeNode(preorder,inorder,rootVal+1,end);
        return root;
    }
    private int findRootVal(int[] inorder, int begin, int end, int rootVal) {
        for (int i = begin; i <= end; i++) {
            if(inorder[i]==rootVal){
                return i;
            }
        }
        return -1;
    }

}
